class Solution {
public:
    string shortestPalindrome(string s) {
        long long left = 0,right = 0;
        long long base = 31,mul = 1;
        long long mod = 1000000007;
        int maxLen = 0;
        for(int i = 0;i < s.size();i++){
            left = (left * base + s[i]) % mod;
            right = (right + mul * s[i]) % mod;
            if(left == right){
                maxLen = i + 1;
            }
            mul = (mul * base) % mod;
        }
        if(maxLen == s.size()) return s;
        string ss = s.substr(maxLen,s.size() - maxLen);
        reverse(ss.begin(),ss.end());
        return ss + s;
    }
};
